package com.leetcode.partition11;

import java.util.HashSet;
import java.util.Set;

/**
 * @author `RKC`
 * @date 2021/12/23 16:15
 */
public class LC1044最长重复子串 {

    private static final int P = 13331, N = (int) (3 * 1e4);
    private static long[] prefix = new long[N], hash = new long[N];

    public static void main(String[] args) {
        System.out.println(longestDupSubstring("banana"));
    }

    public static String longestDupSubstring(String s) {
        //二分枚举答案的长度，每个长度使用字符串哈希进行判断
        stringHash(s);
        int left = 0, right = s.length();
        String answer = "";
        while (left < right) {
            int mid = (left + right) >>> 1;
            String res = check(s, mid);
            if (res.length() != 0) left = mid + 1;
            else right = mid;
            answer = answer.length() < res.length() ? res : answer;
        }
        return answer;
    }

    private static String check(String s, int length) {
        //找出在字符串s中重复出现的字符串，且长度为length
        Set<Long> set = new HashSet<>();
        for (int i = 1; i + length - 1 <= s.length(); i++) {
            int j = i + length - 1;
            long h = substringHash(i, j);
            if (set.contains(h)) return s.substring(i - 1, j);
            set.add(h);
        }
        return "";
    }

    private static void stringHash(String s) {
        prefix[0] = 1;
        for (int i = 1; i <= s.length(); i++) {
            prefix[i] = prefix[i - 1] * P;
            hash[i] = hash[i - 1] * P + s.charAt(i - 1);
        }
    }

    private static long substringHash(int i, int j) {
        return hash[j] - hash[i - 1] * prefix[j - i + 1];
    }
}
